#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 
# Copyright (c) 2017 Baidu.com, Inc. All Rights Reserved
# 

"""
File: run33.py
Author: zhangyang(zhangyang40@baidu.com)
Date: 2018/1/8 0008 15:25
"""
"""
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组,求出这个数组中的逆序对的总数P。
并将P对1000000007取模的结果输出。 即输出P%1000000007

题目保证输入的数组中没有的相同的数字

数据范围：

	对于%50的数据,size<=10^4

	对于%75的数据,size<=10^5

	对于%100的数据,size<=2*10^5
	
输入
1,2,3,4,5,6,7,0
输出
7
"""

import copy as cp


class Solution:
    def inversePairs(self, data):
        if not data:
            return 0
        copy = cp.copy(data)
        count = self.inversePairsCore(data, copy, 0, len(data) - 1)
        return 0

    def inversePairsCore(self, array, copy, low, high):
        if low == high:
            return 0
        mid = (low + high) >> 1
        left_count = self.inversePairsCore(array, copy, low, mid) % 1000000007
        right_count = self.inversePairsCore(array, copy, mid + 1, high) % 1000000007
        count = 0
        i = mid
        j = high
        loc_copy = high
        while i >= low and j > mid:
            if array[i] > array[j]:
                count += j - mid
                loc_copy -= 1
                i -= 1
                copy[loc_copy] = array[i]
                if count >= 1000000007:
                    count %= 1000000007
            else:
                loc_copy -= 1
                j -= 1
                copy[loc_copy] = array[j]
        while i >= low:
            loc_copy -= 1
            copy[loc_copy] = array[i]
            i -= 1
        while j > mid:
            loc_copy -= 1
            copy[loc_copy] = array[j]
            j -= 1
        for s in range(low, high):
            array[s] = copy[s]
        return (left_count + right_count + count) % 1000000007
